#ifndef _contest_bigint_h_
#define _contest_bigint_h_

#include<iostream>
#include<stdint.h>
#include<vector>

using namespace std;

namespace contest
{
/**
 * Unsigned big integer.
 **/
class bigint
{
private:
    vector<uint8_t> digs;
public:
    bigint()
    {
        digs.push_back(0);
    }
    bigint(uint64_t n)
    {
        for (; n > 0; n /= 10)
            digs.push_back(n % 10);
    }
    uint64_t operator %(const uint64_t base) const
    {
        uint64_t remainder = 0;
        for (int i=digs.size()-1; i>=0; --i)
            remainder = (10*remainder + digs[i])%base;
        return remainder;
    }
    bigint& operator *=(const uint64_t n)
    {
        vector<uint8_t> tmp;
        uint64_t remainder = 0;
        for (size_t i=0; i<digs.size(); i++ )
        {
            remainder = digs[i]*n + remainder;
            tmp.push_back(remainder%10);
            remainder/= 10;
        }
        for (; remainder > 0; remainder /= 10)
            tmp.push_back(remainder % 10);
        digs.resize(tmp.size());
        for (size_t i=0; i<tmp.size(); ++i)
            digs[i] = tmp[i];
        return *this;
    }
    bigint operator *(const uint64_t n) const
    {
        bigint result = *this;
        result *= n;
        return result;
    }
    bigint& operator /=(const uint64_t n)
    {
        vector<uint8_t> tmp;
        uint64_t remainder = 0;
        for (size_t i=digs.size()-1; i>=0; --i)
        {
            remainder = 10*remainder + digs[i];
            if (remainder >= n)
            {
                tmp.push_back(remainder/n);
                remainder %= n;
            }
            else if (tmp.size() > 0)
                tmp.push_back(0);
        }
        digs.resize(tmp.size());
        for (size_t i=0; i<tmp.size(); ++i)
            digs[i] = tmp[i];
        return *this;
    }
    bigint operator /(const uint64_t n) const
    {
        bigint result = *this;
        result /= n;
        return result;
    }
    uint64_t toInteger()
    {
        uint64_t res = 0;
        for (int i=digs.size()-1; i>=0; --i)
            res = res*10 + digs[i];
        return res;
    }
    friend ostream& operator<<(ostream& out, const bigint& n)
    {
        for (int i=n.digs.size()-1; i>=0; --i)
            cout<<((uint32_t)n.digs[i]);
    }
};
}

#endif

